#ifndef ALGO_H_
#define ALGO_H_

#include <algorithm>
#include <string>
#include <vector>


namespace lxj
{
// 累加和大于等于target的最短子数组长度
// 给定一个含有 n 个正整数的数组和一个正整数 target
// 找到累加和 >= target 的长度最小的子数组并返回其长度
// 如果不存在符合条件的子数组返回0
// 测试链接 : https://leetcode.cn/problems/minimum-size-subarray-sum/
inline int minSubArrayLen(int target, std::vector<int>& nums)
{
    constexpr int MAX = ~(1 << 31);
    int           ans = MAX;
    for (int r = 0, l = 0, sum = 0; r < nums.size(); r++) {
        sum += nums[r];
        while (sum >= target) {
            ans = ans > r - l + 1 ? r - l + 1 : ans;
            sum -= nums[l++];
        }
    }
    return ans == MAX ? 0 : ans;
}

// 无重复字符的最长子串
// 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
// 测试链接 : https://leetcode.cn/problems/longest-substring-without-repeating-characters/
inline int lengthOfLongestSubstring(std::string s)
{
    // 自己的
    /* if (s.size() == 1) return 1;
    int                           ans = 0;
    std::unordered_map<char, int> map;
    int                           l = 0, r = 0;
    for (; r < s.size(); r++) {
        while (map.count(s[r]) != 0 && r < s.size()) {
            ans = ans > r - l ? ans : r - l;
            l   = l > map[s[r]] ? l : map[s[r]] + 1;
            map.erase(s[r]);
            map[s[r++]] = r;
        }
        map[s[r]] = r;
    }
    r = s.size();
    if (map.count(s[r - 1]) != 0) {
        ans = ans > r - l ? ans : r - l;
    }
    return ans; */

    // 左神版
    int n         = s.size();
    int last[256] = {};
    std::fill(last, last + 256, -1);
    int ans = 0;
    for (int l = 0, r = 0; r < n; r++) {
        l          = std::max(l, last[s[r]] + 1);
        ans        = std::max(ans, r - l + 1);
        last[s[r]] = r;
    }
    return ans;
}

/*给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t
 所有字符的子串，则返回空字符串 ""*/
// 测试链接：https://leetcode.cn/problems/minimum-window-substring/
inline std::string minWindow(const std::string& s, const std::string& t)
{
    int cnts[256]{};
    for (auto c : t) cnts[c]--;
    constexpr int MAX   = ~(1 << 31);
    int           len   = MAX;
    int           start = 0;
    int           debt  = t.size();
    for (int l = 0, r = 0; r < s.size(); r++) {
        cnts[s[r]]++ < 0 ? debt-- : (int)0;
        if (debt == 0) {
            while (cnts[s[l]] > 0) cnts[s[l++]]--;
            if (r - l + 1 < len) {
                len   = r - l + 1;
                start = l;
            }
        }
    }
    return len == MAX ? "" : s.substr(start, len);
}

// 加油站
// 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
// 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
// 你从其中的一个加油站出发，开始时油箱为空。
// 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周
// 则返回出发时加油站的编号，否则返回 -1
// 如果存在解，则 保证 它是 唯一 的。
// 测试链接 : https://leetcode.cn/problems/gas-station/
inline int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost)
{
    int n = gas.size();
    for (int l = 0, r = 0, sum; l < n; l = r + 1, r = l) {
        sum = 0;
        while (sum + gas[r % n] - cost[r % n] >= 0) {
            if (r - l + 1 == n) return l;
            sum += gas[r % n] - cost[r % n];
            r++;
        }
    }
    return -1;
}

// 替换子串得到平衡字符串
// 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
// 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
// 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
// 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
// 请返回待替换子串的最小可能长度。
// 如果原字符串自身就是一个平衡字符串，则返回 0。
// 测试链接 : https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
inline int balancedString(std::string s)
{
    const int n       = s.size();
    int*      str     = new int[n];
    int       cnts[4] = {};
    for (int i = 0; i < n; i++) {
        str[i] = s[i] == 'W' ? 1 : s[i] == 'E' ? 2 : s[i] == 'R' ? 3 : 0;
        cnts[str[i]]++;
    }
    int debt = 0;
    for (int i = 0; i < 4; i++) {
        if (cnts[i] < n / 4) {
            cnts[i] = 0;
        }
        else {
            cnts[i] = n / 4 - cnts[i];
            debt -= cnts[i];
        }
    }

    if (debt == 0) return 0;
    int ans = ~(1 << 31);
    for (int l = 0, r = 0; r < n; r++) {
        if (cnts[str[r]]++ < 0) debt--;
        if (debt == 0) {
            while (cnts[str[l]] > 0) cnts[str[l++]]--;
            ans = ans < r - l + 1 ? ans : r - l + 1;
        }
    }
    delete[] str;
    return ans;
}

// K个不同整数的子数组
// 给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。
// 如果 nums 的某个子数组中不同整数的个数恰好为 k
// 则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
// 例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
// 子数组 是数组的 连续 部分。
// 测试链接 : https://leetcode.cn/problems/subarrays-with-k-different-integers/
inline int subarraysWithKDistinct(std::vector<int>& nums, int k)
{
    auto f = [](std::vector<int>& nums, int k) {
        constexpr int MAXN       = 20001;
        static int    cnts[MAXN] = {};
        std::fill(cnts, cnts + MAXN, 0);
        int ans = 0;
        for (int l = 0, r = 0, collect = 0; r < nums.size(); r++) {
            if (++cnts[nums[r]] == 1) collect++;
            while (collect > k) {
                if (--cnts[nums[l++]] == 0) collect--;
            }
            ans += r - l + 1;
        }
        return ans;
    };
    return f(nums, k) - f(nums, k - 1);
}

// 至少有K个重复字符的最长子串
// 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串
// 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
// 如果不存在这样的子字符串，则返回 0。
// 测试链接 : https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
inline int longestSubstring(std::string s, int k)
{
    int n         = s.size();
    int cnts[256] = {};
    int ans       = 0;
    for (int require = 1; require <= 26; require++) {
        std::fill(cnts, cnts + 256, 0);
        for (int l = 0, r = 0, collect = 0, satisfy = 0; r < n; r++) {
            cnts[s[r]]++;
            if (cnts[s[r]] == 1) {
                collect++;
            }
            if (cnts[s[r]] == k) {
                satisfy++;
            }
            while (collect > require) {
                if (cnts[s[l]] == 1) {
                    collect--;
                }
                if (cnts[s[l]] == k) {
                    satisfy--;
                }
                cnts[s[l++]]--;
            }
            if (satisfy == require) ans = ans > r - l + 1 ? ans : r - l + 1;
        }
    }
    return ans;
}
}   // namespace lxj

#endif